package com.yuan.algorithms.分治算法;

import java.util.Arrays;
import java.util.Random;


/**
 * 使用分治思想来实现归并排序
 * 归并排序是稳定排序，它也是一种十分高效的排序。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。
 * 归并牌序每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序是稳定算法，它的最好，最坏，平均时间复杂度均为O(nlogn)。
 *
 * @author YouYuan
 * @date 2022/3/21 19:01
 */
public class MergeSort {

    public static void main(String[] args) {
        int size = 100000;
        int[] randomArr = SortUtil.randomArr(size);
        int[] clone = randomArr.clone();

        long s = System.currentTimeMillis();
        mergeSort(randomArr);
        long e = System.currentTimeMillis();
        System.out.printf("mergeSort排序耗时：%d(ms)%n", (e-s));
        SortUtil.validateSort(randomArr);

        s = System.currentTimeMillis();
        SortUtil.bubbleSort(clone);
        e = System.currentTimeMillis();
        System.out.printf("bubbleSort排序耗时：%d(ms)%n", (e-s));
        SortUtil.validateSort(clone);
    }

    private static void mergeSort(int[] arr) {
        //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int[] tempArr = new int[arr.length];
        msort(arr, 0, arr.length-1, tempArr);
    }

    /**
     * 采用分治思想，将一个大数组不断拆分成两个子数组，直至不可拆分，最终将有序子数组合并为排好序的大数组
     * @param arr
     * @param left
     * @param right
     * @param tempArr
     */
    private static void msort(int[] arr, int left, int right, int[] tempArr) {
        if (left < right) {
            int mid = (left + right) >> 1;
            msort(arr, left, mid, tempArr);//排序左子序列
            msort(arr, mid+1, right, tempArr);//排序右子序列
            merge(arr, left, mid, right, tempArr);//合并左右序列
        }
    }

    /**
     * 合并两个有序子数组
     * @param arr 原数组
     * @param left 左子序列开始下标
     * @param mid 左子序列结束下标，mid+1即右子序列开始下标
     * @param right 右子序列结束下标
     * @param tempArr 保存归并排序后的临时数据，用于回写原数组
     */
    private static void merge(int[] arr, int left, int mid, int right, int[] tempArr) {
        int leftIndex = left;//左子序列起始下标
        int rightIndex = mid + 1;//右子序列起始下标
        int cur = 0;//当前排序元素下标
        //循环对比左右子序列，将排序后的列表写入临时数组
        while (leftIndex <= mid && rightIndex <= right) {
            if (arr[leftIndex] < arr[rightIndex]) {
                tempArr[cur++] = arr[leftIndex++];
            } else {
                tempArr[cur++] = arr[rightIndex++];
            }
        }
        //将左序列剩余元素写入临时数组后面
        while (leftIndex <= mid) {
            tempArr[cur++] = arr[leftIndex++];
        }
        //将右序列剩余元素写入临时数组后面
        while (rightIndex <= right) {
            tempArr[cur++] = arr[rightIndex++];
        }
        //将合并排序好的数据写回原数组
        for (int i = 0; i < cur; i++) {
            arr[left + i] = tempArr[i];
        }
    }

}
